#include <iostream>
using namespace std;

// 定义ElemType为int类型
typedef int ElemType;

/// @brief 查找表的数据结构（顺序表）
typedef struct
{
    ElemType *elem; // 动态数组基址
    int TableLen;   // 表的长度
} SSTable;

/// @brief 折半查找(条件：数组已经有序)
/// @param L
/// @param key
/// @return
int Binary_Search(SSTable L, ElemType key)
{
    int low = 0, high = L.TableLen - 1, mid;
    while (low <= high)
    {
        mid = (low + high) / 2; // 取中间位置
        if (L.elem[mid] == key)
        {
            return mid; // 查找成功则返回所在位置
        }
        else if (L.elem[mid] > key)
        {
            high = mid - 1; // 从前半部分继续查找
        }
        else
        {
            low = mid + 1; // 从后半部分继续查找
        }
    }
    return -1; // 查找失败，返回-1
}

//////////////////////////5叉查找树//////////////////////////////////////////////////////
typedef int ElemType;
/// @brief 5叉排序树的节点定义
struct Node
{
    ElemType keys[4];      // 最多四个关键字
    struct Node *child[5]; // 最多5个孩子
    int num;               // 节点中有几个关键字
};
